package hot100.logos41To50;

import hot100.datastruct.TreeNode;

import java.util.HashMap;

/**
 * @author logos
 * date 2025/7/14 12:33
 * @version v1.0
 * @Package hot100.logos41To50
 */
public class logos47 {

    /**
     * 47. 从前序与中序遍历序列构造二叉树
     * https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        private HashMap<Integer, Integer> map = new HashMap<>();

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            map.clear();
            for (int i = 0; i < inorder.length; i++) {
                map.put(inorder[i], i);
            }
            return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
        }

        private TreeNode build(int[] pre, int l1, int r1, int[] in, int l2, int r2) {
            if (l1 > r1) {
                return null;
            }
            TreeNode root = new TreeNode(pre[l1]);
            if (l1 == r1) {
                return root;
            }
            int k = map.get(pre[l1]);
            root.left = build(pre, l1 + 1, l1 + k - l2, in, l2, k - 1);
            root.right = build(pre, l1 + k - l2 + 1, r1, in, k + 1, r2);
            return root;
        }
    }
}
